Colmap论文

  最近又将Colmap论文翻出来仔细阅读总结了一下，于是顺便写个博客记录一下。Structure-from-Motion Revisited是当前SOTA的增量式SfM算法Colmap的论文，发表于2016年计算机视觉顶会CVPR。它是增量式SfM里程碑式的作品。

  如上图所示，作者将其分成两大部分：Correspondence Search和Incremental Reconstruction。   Correspondence流程是：首先对所有的输入图像进行特征提取，这通常是由稳健的SIFT算法实现的；然后使用提取的特征点描述子进行匹配，一种暴力方法是穷举所有可能的匹配对，但是这在大场景情形下是不可接受的；匹配完成后，还需要使用对极几何关系对每个匹配图像对里的匹配点对进行精化，因为通常会存在很多误匹配点对。   Incremental Reconstruction流程是：初始化部分是寻找一对初始的匹配图像对，这个图像对的选择对后面的重建过程非常重要，所以通常需要精心筛选。论文提到，初始图像对之间的匹配点数量越多，通常可以获得更为鲁棒和精确的结果；而如果匹配点数量较为稀疏，则重建速度会更快，因为BA（Bundle Adjustment）求解的问题较小。选定匹配对后，利用对极几何关系分解获得两张图像的位姿，然后三角化生成三维点。接下来，每次往系统中增加一张新的图像，通过PnP（Perspective-n-Point）估计它的位姿，然后三角化生成新的三维点，之后进行BA优化，BA过程中滤除外点。直至所有图像都被加入系统中。   

  作者认为，现有的SfM系统在重建的完整性和鲁棒性（completeness and robustness）上还是存在缺陷。本文对此进行了改进，主要贡献包括：

  利用合适的几何关系去增强场景图，内容包括：

  下一最佳视图选择对位姿估计的质量、三角化的完整性与精度都有很大影响。作者提到，一个流行的方法是，找到一张能观察到最多已经三角化过的点的图像。但是，有时该图像的观测条件数并不好。有研究表明，如果匹配点的分布越均匀，那么其重建的结果也会更好。因此，作者提出一种使用多尺度格网来度量匹配点分布状况的方法。   如上图所示，作者将图像划分成不同尺度格网，然后对不同尺度的格网点分布状况进行打分，这样可以同时考虑到点的数量与分布的影响。总的来说，点的数量越多，分布越均匀，则该图像的得分越高。上图中纵向是点分布的差异与得分差异的对比，横向是点数量与得分的对比。分数的计算方式如下所示：   对不同匹配图像进行打分后，选择得分最高的图像作为下一最佳匹配图像。实验表明，使用该策略可以提升重建的鲁棒性和精度。   

  作者提出了一种高效的、基于采样的三角化方法，它可以从受异常值污染的特征点中鲁棒地估计出三维点。三角化的公式如下所示。其中τ指代任意一种三角化的方式，Colmap里用的是DLT（Direct Linear Transform，直接线性变换）。   作者不对全景图像进行三角化，它们可能因为错误的位姿估计而生成错误的三角化点。一个适合于三角化的图像对应该满足如下三个条件：

  作者使用RANSAC方法对三角化点进行采样，从而剔除outliers的影响。实验表明，所提出方法可以在提高三角化完整性的同时减少计算量。   

  作者提出的BA优化策略是：在每次增加一张新图像后，只对与该图像有最大关联的一部分图像进行局部BA。当模型增加一定比例之后，才进行一次全局BA。这样做可以减少计算的代价。

  使用Cauchy核函数作为鲁棒损失函数来应对outliers的影响。依据不同大小的重建问题，使用不同的求解策略。对于数百张图像的情况，使用sparse方法进行求解；对于更多张的图像，使用PCG进行求解。对不同问题，采用不同的相机模型进行求解。

  每次BA过程中，将重投影误差较大的三维点过滤掉。在优化过程中，使相机焦距和畸变参数自由优化，然后在全局BA后，将视野不正常或者畸变参数大的相机视为错误估计，并进行剔除。

  为了提高重建场景的完整性，对于先前被过滤掉的但是偏差不是很大的三维点进行再三角化。不提高三角化的阈值，只对误差低于过滤阈值的观测进行再三角化。

  由于漂移（drift）或者错误的位姿估计，通常会有很大一部分三维点被错误滤除，而使用两步BA可以显著提升结果精度。因此，迭代进行BA、RT、过滤，直到被滤除的观测点和再三角化点减少。大多数场景下，在第二轮迭代过后，结果就会有显著的提升了。   

  BA是SfM性能的瓶颈。因此，作者针对大重叠度场景提出一种高效的相机分组优化策略，代替了昂贵的图割操作。与将很多相机聚类到一个子图上相比，作者将场景分割成很多小的、高度重叠的相机组，然后将每组相机使用一个（自由）相机来代替（这样可以减少BA优化过程中自由参数的数量）。   通过图像之间的共视程度来决定哪幅图像归于同一组。具体的，对于一个具有n个三维点的场景，使用一个{0，1}向量来表示每张图像的观测，若观测到该三维点，则为1，否则为0。然后通过交集/并集来获得共视程度，如下式所示：   若共视程度大于阈值且组内图像数量小于阈值，则将该图像加入该组。在每组内使用局部坐标系来参数化组内的相机。针对图像组的BA损失函数如下式所示：   其中，Gr是图像组共用的外参，Pc是组内每张图像的位姿。在进行优化的时候，组内每张图像的位姿为Pcr=PcGr，其中Pc在优化过程中固定不变，Gr可变。如此，BA优化时候，自由变量的数量就大大减少了。   

  Colmap针对当前SfM存在的问题进行了充分的改进，它针对增量式重建的每一个步骤都提出了新的优化方法，从而提高了重建场景的完整性、鲁棒性、精度、效率等。虽然该论文是2016年提出的，但时至今日，它仍被认为是SOTA的增量式SfM算法，仍有很强的借鉴意义。